#include<stdio.h>//操作系统-内存分配问题/伙伴算法
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#define M 11  //最大可分配空间为1024

//定义数据结构：二叉树结点结构
struct buddynode
{
    char name;//进程名
    int level; //内存空间大小：2^level
    int flg;//1-空闲，0-已分配
    int loca;//1-右孩子,0-左孩子
    struct buddynode *next;
    struct buddynode *lkid;//左孩子
    struct buddynode *rkid;//右孩子
    struct buddynode *parent;//父
};
struct buddynode *Wei[M];//空间大小为2^M的空闲队列，尾指针，指向空闲队列最后一个空闲区
struct buddynode *Head[M];//空闲队列头指针
struct buddynode *ab;//初始化时指向根结点，每次遍历使用
struct buddynode *Abs;//暂存结点信息
struct buddynode *bt;//存储要释放内存的信息

void initSpace()//初始化内存空间
{
    int i;
    for(i=0;i<M-1;i++)//建立空闲队列
    {
        Head[i]=(buddynode*)malloc(sizeof(buddynode));
        Wei[i]=NULL;
        Head[i]->next=NULL;
    }
    Wei[M-1]=(buddynode*)malloc(sizeof(buddynode));
    Wei[M-1]->name=NULL;
    Wei[M-1]->level=M-1;
    Wei[M-1]->flg=1;
    Wei[M-1]->loca=NULL;//表示是根结点
    Wei[M-1]->next=NULL;
    Wei[M-1]->lkid=NULL;
    Wei[M-1]->rkid=NULL;
    Wei[M-1]->parent=NULL;
    Head[M-1]=(buddynode*)malloc(sizeof(buddynode));
    Head[M-1]->next=Wei[M-1];
    ab=Wei[M-1];//指向根结点
}

void alloc(char n,int m)//分配，n-进程名，m-空间大小
{
    int k,sj,si;
    buddynode *x;
    buddynode *y;//空闲结点删除后暂存y
    k=m;
    si=0;
    while(k>0)//level增加
    {
        k=k/2;
        si+=1;
    }
    //判断是否存在大小为si的空闲区
    if((Head[si]->next!=NULL)&&(Wei[si]!=NULL))
    {
        y=Head[si]->next;
        if(y->next==NULL)
        {
            Head[si]->next=NULL;
            Wei[si]=NULL;
        }
        else{
            Head[si]->next=(Head[si]->next)->next;
        }
        y->name=n;
        y->flg=0;
        y->next=NULL;
    }
    //没有合适大小的空间，向上层找
    else
    {
        sj=si;
        //while循环直到找到非空队列
        while(sj<M-1)
        {
            if((Head[sj]->next==NULL)||(Wei[sj]==NULL))
            {
                sj+=1;
            }
            else break;
        }
        if(sj==M)//没有可分配的空间
        printf("NULL");
        else//从Wei[sj]中拿出第一个结点开始分配
        {
            x=Head[sj]->next;
            if(x==Wei[sj])
            {
                Head[sj]->next=NULL;
                Wei[sj]=NULL;
            }
            else
            Head[sj]->next=(Head[sj]->next)->next;
            //循环分配，对半
            for(k=sj;k>si;k--)
            {
                x->rkid=(buddynode*)malloc(sizeof(buddynode));
                x->lkid=(buddynode*)malloc(sizeof(buddynode));
                (x->rkid)->name=NULL;
                (x->rkid)->level=k-1;
                (x->rkid)->flg=1;
                (x->rkid)->loca=1;
                (x->rkid)->next=NULL;
                (x->rkid)->lkid=NULL;
                (x->rkid)->rkid=NULL;
                (x->rkid)->parent=x;
                //右孩子加入对应空闲分区，左孩子继续分配
                if(Wei[k-1]==NULL)
                {
                    Wei[k-1]=x->rkid;
                    Head[k-1]->next=Wei[k-1];
                }
                else
                {
                    Wei[k-1]->next=(buddynode*)malloc(sizeof(buddynode));
                    Wei[k-1]->next=x->rkid;
                    Wei[k-1]=Wei[k-1]->next;
                }
                (x->lkid)->name=NULL;
                (x->lkid)->level=k-1;
                (x->lkid)->flg=0;
                (x->lkid)->loca=0;
                (x->lkid)->next=NULL;
                (x->lkid)->parent=x;
                x=x->lkid;//x指向左孩子，继续下一循环，再分配
            }
            //此时，x已指向要分配的空间，对x进行操作，将其分配给进程
            x->name=n;
            x->lkid=NULL;
            x->rkid=NULL;
        }
    }
}

void present(buddynode* Abs)//显示当前分配情况，操作时abs=ab
{
    int z;
    if(Abs!=NULL)
    {
        if((Abs->lkid==NULL)&&(Abs->rkid==NULL))
        {
            z=pow(2,Abs->level);
            if(Abs->flg==1)//当空闲
            printf("| %d ",z);
            else//当被占用
            printf("| %c %d ",Abs->name,z);
        }
        else{
            present(Abs->lkid);
            present(Abs->rkid);
        }
    }
}

//定义二叉树查找函数，递归查找，找到要释放的进程对应的空间，返回该空间指针，用于释放空间
buddynode* find(char n,buddynode* Abs)
{
    if(Abs!=NULL)
    {
        if(Abs->name==n)//找到对应进程，将该内存信息存入bt
    {
        bt=Abs;
    }
    else{
        if(!find(n,Abs->lkid))
        {
            find(n,Abs->rkid);
        }
    }
    }
}

//释放空间：bt为先前找到的空间指针
void release(buddynode *bt)
{
    buddynode* br;
    buddynode* bl;
    buddynode* bf;
    if(bt!=NULL)
    {
        if(bt->loca==0)//判断为左孩子，则与右孩子合并
        {
            if(((bt->parent)->rkid)->flg==0)//判断其兄弟结点是否空闲，若非空闲，将该结点加入空闲队列
            {
                bt->name=NULL;
                bt->flg=1;
                if(Wei[bt->level]==NULL)
                {
                    Wei[bt->level]=bt;
                    Head[bt->level]->next=Wei[bt->level];
                    bt=NULL;
                }
                else{
                    Wei[bt->level]->next=(buddynode*)malloc(sizeof(buddynode));
                    Wei[bt->level]->next=bt;
                    bt=NULL;
                }
            }
            else{//兄弟结点空闲
                (bt->parent)->flg=1;
                br=(bt->parent)->rkid;//br指向其兄弟结点
                bf=Head[br->level];//bf用来寻找br在空闲队列中的位置
                while((bf->next)!=br)
                {
                    bf=bf->next;
                }
                bf->next=(bf->next)->next;//找到bf,将其从空闲队列删除
                (bt->parent)->lkid=NULL;
                (bt->parent)->rkid=NULL;//左右孩子回收，所以为空
                bt=bt->parent;//指针指回父母，重新进入while循环
                if(bt==ab)//为根结点，空置
                {
                    bt->flg=1;
                    Wei[M-1]=bt;
                    Head[M-1]->next=Wei[M-1];
                }
            }
        }
        else//判断是右孩子，同上
        {
            if(((bt->parent)->lkid)->flg==0)
            {
                bt->name=NULL;
                bt->flg=1;
                if(Wei[bt->level]==NULL)
                {
                    Wei[bt->level]=bt;
                    Head[bt->level]->next=Wei[bt->level];
                    bt=NULL;
                }
                else{
                    Wei[bt->level]->next=(buddynode*)malloc(sizeof(buddynode));
                    Wei[bt->level]->next=bt;
                    bt=NULL;
                }
            }
            else{
                (bt->parent)->flg=1;
                bl=(bt->parent)->lkid;
                bf=Head[bl->level];
                while((bf->next)!=bl)
                {
                    bf=bf->next;
                }
                bf->next=(bf->next)->next;
                (bf->parent)->lkid=NULL;
                (bt->parent)->rkid=NULL;
                bt=bt->parent;
                if(bt==ab)
                {
                    bt->flg=1;
                    Wei[M-1]=bt;
                    Head[M-1]->next=Wei[M-1];
                }
            }
        }
    }
}

int main()
{
    int num;//选择序号
    char name;//进程名
    int size,sum;//空间大小，随机生成数的范围，这里设为2^7
    do
    {
        printf("\n\n1.内存初始化\t2.分配内存\t3.回收内存\t4.显示情况\n\n请选择序号：");
        scanf("%d",&num);
        switch(num)
        {
            case 1:
                initSpace();
                Abs=ab;
                present(Abs);
                break;
            case 2:
                printf("请输入进程名：\n ");
                getchar();
                scanf("%c",&name);
                sum=pow(2,M-4);
                size=rand()%(sum+1);
                printf("确认请求分配的进程名、空间大小是： %c , %d\n",name,size);
                alloc(name,size);
                Abs=ab;
                present(Abs);
                break;
            case 3:
                printf("请输入要回收的进程名： ");
                getchar();
                scanf("%c",&name);
                printf("确认要回收的进程是：%c\n",name);
                Abs=ab;
                find(name,Abs);//找到要回收的内存单元
                release(bt);
                present(Abs);
                break;
            case 4:
                Abs=ab;
                printf("此时内存使用情况：\n");
                present(Abs);
                break;
        }
    } while (num!=0);

    return 0;
}